package com.lw.leetcode.back;

import java.util.Arrays;

/**
 * 1723. 完成所有工作的最短时间
 *
 * @Author liw
 * @Date 2021/5/8 9:10
 * @Version 1.0
 */
public class MinimumTimeRequired {
    private long minId = Integer.MAX_VALUE;

    public static void main(String[] args) {
        MinimumTimeRequired test = new MinimumTimeRequired();
//        int[] jobs = {1, 2, 4, 7, 8};
        int[] jobs = {3,2,3};
        int k = 3;

        int i = test.minimumTimeRequired1(jobs, k);
        System.out.println(i);
        test.minId = Integer.MAX_VALUE;
         int c = test.minimumTimeRequired(jobs, k);
        System.out.println(c);
    }

    public int minimumTimeRequired(int[] jobs, int k) {
        int[] ints = new int[k];
        find(jobs, ints, 0, 0);
        System.out.println(Arrays.toString(ints));
        return (int) minId;
    }

    private void find(int[] jobs, int[] times, int m, int minTime) {
        boolean first = true;
        for (int i = 0; i <  times.length; i++) {
            times[i] += jobs[m];
            int a = Math.max(times[i], minTime);
            if (a <= minId) {
                if (m + 1 == jobs.length) {
                    minId = Math.min(a, minId);
                    times[i] -= jobs[m];
                    return;
                }
                find(jobs, times, m + 1, a);
            }
            times[i] -= jobs[m];
            if (times[i] == 0 && !first) {
                return;
            }
            if (times[i] == 0) {
                first = false;
            }
        }
    }

    public int minimumTimeRequired1(int[] jobs, int k) {
        long[] ints = new long[k];
        fd3(jobs, ints, 0, 0);
        System.out.println(Arrays.toString(ints));
        return (int) minId;
    }

    private void fd1(int[] jobs, int[] times, int m, int minTime) {
        if (m == jobs.length) {
            minId = Math.min(minTime, minId);
            return;
        }
        for (int i = 0; i < times.length; i++) {
            times[i] += jobs[m];
            fd1(jobs, times, m + 1, Math.max(minTime, times[i]));
            times[i] -= jobs[m];
        }
    }

    // 然后，执行到k=9的时候就超时了,开始第一次剪枝，如果当前的最少时间已经超过已遍历过的最少时间，就停止搜索，代码是这样的
    private void fd2(int[] jobs, long[] times, int m, long minTime) {
        if (m == jobs.length) {
            minId = Math.min(minTime, minId);
            return;
        }
        for (int i = 0; i < times.length; i++) {
            times[i] += (long) jobs[m];
            long tmpMax = Math.max(minTime, times[i]);
            if (tmpMax < minId) {
                fd2(jobs, times, m + 1, Math.max(minTime, times[i]));
            }
            times[i] -= (long) jobs[m];
        }
    }

    // 然后，这一次坚挺到了k=10,依然超时，所以开始第二次剪枝。
    //仔细思考可以发现，用回溯分配任务时，不同工人的不同顺序，是当作两种状态的，而实际分配任务对工人的顺序是无所谓的，所以回溯不可避免的出现了很多重复的状态。
    //方法也很简单，就是每次分配任务，如果前面有人是没有任务的，就停止搜索，代码如下
    private void fd3(int[] jobs, long[] times, int m, long minTime) {
        if (m == jobs.length) {
            minId = Math.min(minTime, minId);
            return;
        }
        boolean first = true;
        for (int i = 0; i < times.length; i++) {
            if (times[i] == 0L && !first) {
                return;
            }
            if (times[i] == 0L) {
                first = false;
            }
            times[i] += (long) jobs[m];
            long tmpMax = Math.max(minTime, times[i]);
            if (tmpMax < minId) {
                fd3(jobs, times, m + 1, Math.max(minTime, times[i]));
            }
            times[i] -= (long) jobs[m];
            System.out.println(Arrays.toString(times));
        }
    }


}
